﻿#include <stdio.h>
#include <stdlib.h>
#include <string>

#ifndef _LIST_H
#define _LIST_H

typedef struct ListType
{
	int data;
	struct ListType* next;
}ListType;

/*初始化构建一个链表*/
ListType* ListInit()
{
	int length;
	ListType* Head, * Node, * End;
	printf("请输入您构建链表的长度: \n");
	scanf_s("%d", &length);
	while (length == 0 || length < 0)
	{
		printf("您输出的数字错误\n");
		printf("请输入您构建链表的长度: \n");
		scanf_s("%d", &length);
	}
	Head = (ListType*)malloc(sizeof(ListType));
	End = Head;
	printf("请输入节点数据，按Enter进行下一个节点的输入: \n");
	for (int i = 0; i < length; i++)
	{
		Node = (ListType*)malloc(sizeof(ListType));
		scanf_s("%d", &Node->data);
		End->next = Node;
		End = Node;
	}
	End->next = NULL;
	return Head->next;
}

/*打印输出当前链表里的值*/
void PrintfList(ListType* Head)
{
	ListType* RecTemp;
	RecTemp = Head;
	while (RecTemp != NULL)
	{
		printf("%d\n", RecTemp->data);
		RecTemp = RecTemp->next;
	}
}

/*采用头插法进行构建一个新的链表
首先构建一个结点，然后进行插入元素*/
ListType* ReversalList(ListType* Head)
{
	ListType* HeadTemp, * Temp, * next;
	HeadTemp = (ListType*)malloc(sizeof(ListType));
	HeadTemp->next = NULL;
	Temp = Head;
	while (Temp != NULL)
	{
		next = Temp->next;
		Temp->next = HeadTemp->next;
		HeadTemp->next = Temp;
		Temp = next;
	}
	return HeadTemp->next;
}
/*删除相同节点
采用两个指针，循环遍历链表中的元素
方法2：构建一个很大的数组，利用其中的data值小于20000，进行寻找重复的元素*/
ListType* DeletSimpleNode(ListType* Head)
{
	ListType* HeadTemp = Head;
	if (HeadTemp == NULL)
	{
		printf("当前链表是空的，请检查链表");
		return NULL;
	}
	ListType* Current = Head;
	while(Current)
	{
		ListType* P = Current;
		while (P->next)
		{
			if(P->next->data==Current->data)
			{ 
				P->next = P->next->next;
			}
			else
			{
				P = P->next;
			}
		}
		Current = Current->next;
	}
	
	return HeadTemp;
		
}

/*查找倒数第K个元素*/
ListType* FindRecNode(ListType* Head, int Reciprocal)
{
	ListType* former = Head;
	ListType* latter = Head;
	if (Head == NULL || Head->next ==NULL)
		return NULL;
	for (int j = 0; j < Reciprocal; j++)
	{
		former = former->next;
	}
	while (former)
	{
		latter = latter->next;
		former = former->next;
	}
	return latter;
}

/*打印出一个带有结点的链表的中间元素
注意边界条件，少任何一个都会出现问题
可以使用🖊在纸上推算一波*/
ListType* FindMiddleNode(ListType* Head)
{
	ListType* Faster = Head;
	ListType* Latter = Head;
	while ((Faster != NULL) && (Faster->next != NULL))
	{
		Faster = Faster->next->next;
		Latter = Latter->next;
	}
	return Latter;
}
/*反转链表的第二种方法*/
ListType* reverseList(ListType* Head)
{
	if (Head == NULL || Head->next == NULL)
		return Head;
	ListType* former = NULL;
	ListType* middle = Head;
	ListType* latter = NULL;

	while (middle != NULL)
	{
		latter = middle->next;
		middle->next = former;
		former = middle;
		middle = latter;
	}
	return former;
}










#endif
